package personal.leil.learning.exercises;

import personal.leil.learning.SNode;

import java.util.HashSet;
import java.util.Objects;

/**
 * 两个链表求交点的问题
 * <p>
 * 给定两个链表head1和head2，求两个链表相交的点。
 * </p>
 */
public class Question5 {

    /**
     * 求交点
     *
     * @param head1 head for linked list1
     * @param head2 head for linked list2
     * @return array of intersection of both linked list
     */
    public static SNode[] getIntersection(SNode head1, SNode head2) {
        SNode loop1 = hasLoop1(head1);
        SNode loop2 = hasLoop2(head2);
        if (loop1 == null) {
            if (loop2 == null) {
                SNode c1 = head1,
                        c2 = head2;
                while (c1.getNext() != null) {
                    c1 = c1.getNext();
                }
                while (c2.getNext() != null) {
                    c2 = c2.getNext();
                }
                if (c1 == c2) {
                    return new SNode[]{getIntersection(head1, head2, c1)};
                }
            }
        } else {
            if (loop2 != null) {
                if (loop1 == loop2) {
                    return new SNode[]{getIntersection(head1, head2, loop1)};
                } else {
                    return new SNode[]{loop1, loop2};
                }
            }
        }
        return null;
    }


    /**
     * 在两个链表一定有交点的无环链表上求交点
     *
     * @param head1 head for linked list1
     * @param head2 head for linked list2
     * @param last  last node for both linked list
     * @return intersection of both linked list
     */
    public static SNode getIntersection(SNode head1, SNode head2, SNode last) {
        int n = 0;
        SNode c1 = head1,
                c2 = head2;
        while (c1 != last) {
            n++;
            c1 = c1.getNext();
        }
        while (c2 != last) {
            n--;
            c2 = c2.getNext();
        }
        c1 = n > 0 ? head1 : head2;
        c2 = c1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            n--;
            c1 = c1.getNext();
        }
        while (c1 != c2) {
            c1 = c1.getNext();
            c2 = c2.getNext();
        }
        return c1;
    }


    /**
     * 查看链表中是否有环
     * <pre>
     *     额外空间复杂度不做要求，可以使用hashset作为辅助来判断链表是否有环
     * </pre>
     *
     * @param head head for linked list
     * @return node for enter loop
     */
    public static SNode hasLoop1(SNode head) {
        HashSet<SNode> set = new HashSet<>();
        SNode current = head;
        while (current != null) {
            if (set.contains(current)) {
                return current;
            }
            set.add(current);
            current = current.getNext();
        }
        return null;
    }

    /**
     * 查看链表中是否有环
     * <pre>
     *     额外空间复杂度为O(1)，使用快慢指针的原理进行判断
     * </pre>
     *
     * @param head head for linked list
     * @return node for enter loop
     */
    public static SNode hasLoop2(SNode head) {
        if (head == null || head.getNext() == null) {
            return null;
        }
        SNode slow = head.getNext();
        SNode fast = head.getNext().getNext();
        while (!Objects.equals(slow, fast)) {
            if (fast == null || fast.getNext() == null) {
                return null;
            }
            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }
        fast = head;
        while (!Objects.equals(slow, fast)) {
            fast = fast.getNext();
            slow = slow.getNext();
        }
        return fast;
    }

    /********************* For Test *************************/

    public static SNode[] buildLinkedListForTest() {
        SNode head1 = new SNode(12);
        SNode n1 = head1.setNext(new SNode(15));
        SNode n2 = n1.setNext(new SNode(17));
        SNode n3 = n2.setNext(new SNode(8));
        SNode n4 = n3.setNext(new SNode(99));
        SNode n5 = n4.setNext(new SNode(88));
        // 添加环
        n5.setNext(n3);

        SNode head2 = new SNode(44);
        SNode n21 = head2.setNext(new SNode(87));
        SNode n22 = n21.setNext(new SNode(99));
        // 相交
        n22.setNext(n4);
        return new SNode[]{head1, head2};
    }

    public static void main(String[] args) {
        SNode[] heads = buildLinkedListForTest();
        SNode[] intersection = getIntersection(heads[0], heads[1]);
        if (intersection == null) {
            System.out.println("have not intersection!");
            return;
        }
        StringBuilder intersectionStr = new StringBuilder("[");
        for (int i = 0; i < intersection.length; i++) {
            intersectionStr.append(intersection[i]);
            if (i < intersection.length - 1) {
                intersectionStr.append(", ");
            }
        }
        intersectionStr.append("]");
        System.out.println("have intersection: " + intersectionStr);
    }


}
